{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 连续子数组的最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。\n",
    "\n",
    "要求时间复杂度为O(n)。\n",
    "\n",
    " \n",
    "\n",
    "示例1:\n",
    "```\n",
    "输入: nums = [-2,1,-3,4,-1,2,1,-5,4]\n",
    "输出: 6\n",
    "解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。\n",
    "```\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 如何暴力求解?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从第一个元素开始循环\n",
    "```\n",
    "n = len(nums)\n",
    "max_sum = float(\"-inf\")\n",
    "for i in range(n):\n",
    "    for j in range(i, n):\n",
    "        max_sum = max(max_sum, sum(nums[i:j+1]))\n",
    "```     \n",
    "\n",
    "复杂度为 $O^3$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "重叠的子问题为:`max_sum = max(max_sum, sum(nums[i:j+1]))`多次计算了元素的和\n",
    "\n",
    "这边就算优化了,也是 $O^2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 动态规划"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = [-2,1,-3,4,-1,2,1,-5,4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXIAAAD4CAYAAADxeG0DAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3deXjU13no8e+ZGe070oyQBFpYJCEwwrZsNttIXhIvgNs0eZo0m0l70yVNs7fZ2ybNvW2apOlNctObJrGzLzdLG/C+gBdsCQM2oJFAgCQkNBJaBs1ol2bm3D+kITIGrGVmfr/f6P08j54HtJzfiy29OvOec96jtNYIIYSwLpvRAQghhFgcSeRCCGFxksiFEMLiJJELIYTFSSIXQgiLcxjx0Ly8PF1aWmrEo4UQwrKOHDnSr7V2Xv5+QxJ5aWkphw8fNuLRQghhWUqpc1d6v5RWhBDC4iSRCyGExUkiF0IIi5NELoQQFieJXAghLC5iiVwpZVdKvaKU2hepMYUQQryxSM7IPwQ0R3A8IYQQcxCRRK6UWgHcB3w3EuOJ+NY3NMFvXzmPtFAWS8nA8AT/8thJzvYNR3zsSM3Ivw78LRC62icopd6vlDqslDrc19cXoccKK/reC2185BfHaO4eMjoUIWLmeJePbx84S9/QRMTHXnQiV0rtBHq11keu9Xla6+9orWu01jVO5+tOmIolpL51AIDfHfMYHIkQsdPk8QNQVZgZ8bEjMSPfDuxWSrUDPwduV0r9OALjijg0MhHgRJcPgL3HPFJeEUuG2+OjJDeVzOSEiI+96ESutf6U1nqF1roUeDvwjNb6XYuOTMSlw+cuEgxp3nJ9EV2DYxztGDQ6JCFiwu3xsz4Ks3GQfeQixhpaB3DYFJ+8p5Ikh429Ul4RS4B/fIpzA6OsL8yKyvgRTeRa6wNa652RHFPEl4Y2L9etyMKVmcztlS72He8mELzqGrkQcSGa9XGQGbmIodHJAMc6B9lclgvA7upC+ocnaGjzGhyZENHlnknkG6wwIxfiWo6eGyQQ0mxZtQyAukoX6UkOfveqlFdEfHN3+XBlJOHMSIrK+JLIRcw0tA1gtylqSqcTeXKCnTdV5fNoYzcTgaDB0QkRPdFc6ARJ5CKG6lsH2FCYSXrS7y+m2rWpEP94gOdb+g2MTIjoGZ8KcqZvmA1F0SmrgCRyESPjU0GOdfrYsir3Ne+/ZU0eOakJcjhIxK1TPUMEQ1pm5ML6jnZcZDIYYvNMfTwswW7jnusKeLLpAqOTAYOiEyJ6Gj3TB+CitfUQJJGLGKlv9WJTXKqPz7a7upCxqSBPN/caEJkQ0eX2+MlMdrAiJyVqz5BELmKioXWA9YVZVzyefHPpMvIzk6S8IuLS9EJnFkqpqD1DErmIuvGpIK90DrK57PWzcQCbTbFzYyHPnurDNzYV4+iEiJ5AMMTJ7ujuWAFJ5CIGXu0cZDIQYvNlC52z7a4uZDIY4vHGnhhGJkR0ne0bYSIQYn2RJHJhcQ2tXpSaLqFczcYVWZTkprL3uJRXRPxwx2ChEySRixhoaBtg3fJMslKv3r5TKcWujYUcPNMflcb7QhjB7fGTnGBjVV5aVJ8jiVxE1UQgyJFzF1+3f/xKdm8qJKThkRPdMYhMiOhr7PJRuTwThz26qVYSuYiq4+d9TARev3/8SsrzM6hcniGtbUVc0FrTFIOFTpBELqKs/uz0tW7Xqo/Ptqu6kMPnLtI1OBbNsISIuk7vGEPjgagezQ+TRC6iqqHNS+XyDHLSEuf0+bs2FgLIrFxY3u8XOmVGLixsMhCac308rDg3lU0rsyWRC8tr9Piw2xTl+RlRf5YkchE1J7oGGZsKXvUg0NXsri7E7fFztm84SpEJEX1uj5+1rnSSE+xRf5YkchE19a3TN//cPM9Eft/GApRCLpwQlhY+mh8LkshF1DS0eSnPTyc3fX63ouRnJrOlLJe9xz1oraMUnRDR0+sfp29oIib1cZBELqJkKhjicLv30v2c87V7UyGtfSOX7joUwkrC37eSyIWlNXb5GJ0Mzmuhc7a71y/HYVOy6CksKbxjpUoSubCyhraF1cfDctISua3cyb7j3YRCUl4R1uL2+CnNTSXjCm2bo0ESuYiK+tYBVjvTFnVr+O7qQroGxzjacTGCkQkRfY0eX8wWOkESuYiCQDDE4fb57R+/kjur8kly2OTCCWEpvrEpOr1jMSurgCRyEQVN3X6GJwLX7D8+F+lJDu5cl88jJ7oJBEMRik6I6GqaWeiMxdH8MEnkIuLqW6f7q2xZYH18tl3VhfQPT/LSzJhCmF0sj+aHSSIXEdfQ6mVVXhquzORFj1Vb4SQjySGHg4RluD1+8jOTyJvn+YnFkEQuIioY0hxq986pbe1cJCfYedP65Tzm7mEiEIzImEJEkzvGC50giVxEWHO3n6HxwIIPAl3J7k2FDI0HePZUX8TGFCIaxiaDnOkdZkMMyyogiVxEWLg+HqkZOcC21bksS0uU3SvC9E72+AlpqJIZubCyhjYvJbmpFGSlRGzMBLuNe69bzlPNFxiZCERsXCEiLdZH88MkkYuICYU0h9q8bIlgWSVsd3UR41Mhnmq+EPGxhYgUt8dPVkoCK3IiN5GZC0nkImJO9gzhG5uKaFklrKYkh4KsZOm9IkytyeNjfWEmSqmYPlcSuYiYhrZwfTzyM3KbTbFzYwHPtvQxODoZ8fGFWKypYIjmnqGYl1UgAolcKbVSKbVfKdWklHIrpT4UicCE9dS3DrByWQpF2dF5Wbm7uoipoOZxd09UxhdiMc72DTMZCMV86yFEZkYeAD6mta4CtgAfUEpVRWBcYSHh+ngktx1ebkNRJmV5abJ7RZiSuyt8NN+CM3KtdbfW+ujMn4eAZqBoseMKa2npHeLi6NS87+ecD6UUuzYW8NLZAXqHxqP2HLPpG5rgfz99mh7f0vk3W5Hb4yclwU5ZXnrMnx3RGrlSqhS4Hmi4wsfer5Q6rJQ63NcnBzviTcPM/ZyL7Xj4RnZvKiSk4eHj3VF9jpn8w+/cfO3JFuq+coBvPH2a8Sk54WpGjR4flQUZ2G2xXeiECCZypVQ68Gvgw1rr193PpbX+jta6Rmtd43Q6I/VYYRINbQMUZaewcllqVJ+zxpXBuoLMJbN7paF1gIdPdPPuLSXUVjj56pMt3PHVZ3nkRLfcZ2oioZCm2eM3ZKETIpTIlVIJTCfxn2itfxOJMYV1aK1paPVGtawy267qAo52DNLpHY3J84wSDGn+cW8ThVnJfPredXz7XTfy0/+xmYxkB3/1k6O8/Tv1lzrtCWN1XhxlaCLABgMWOiEyu1YU8D2gWWv9tcWHJKzmTO8wAyOTUS+rhO3aWAjA3uPxPSv/5eFOmrr9fOredaQk2gHYtjqPfR+8hX/6gw20XBhi1zde4FO/OcHA8ITB0S5tjV3hE50WTeTAduDdwO1KqVdn3u6NwLjCIupn7ueMxkGgK1m5LJUbirPZeyx+6+S+sSm+8vgpbirNYefGgtd8zGG38a4tJRz4eB0PbCvj/x3upPYrB/ju861MBuQCDiO4PT4cNkX58tgvdEJkdq28oLVWWuuNWutNM2+PRCI4YQ31rQMsz0ymOMr18dl2VRfS3O3nTO9QzJ4ZS994+jTe0Un+ftf6q54SzEpN4PO7qnjsw7dyfXEO//RwM3f/+3PsP9Ub42iF2+NnjSudJIfdkOfLyU6xKOH6+JZVy2J6LPm+jQXYFHF54cTZvmEeerGdP65ZOafrwta4MvjBnpv4/gM1aA17HnyZBx48xJne4RhEK7TWuD2+mF7tdjlJ5GJRWvtH6B+eiMqx/GtxZSSzdXUue4/H3+6NLz3cTHKCnY+9qWLOX6OU4vbKfB7/8G189r51HGm/yN1ff44v7mvCNzYVxWhF79AE/cOThu1YAUnkYpEu9R+P0Y6V2XZtLKStf+TSQlM82H+ql2dO9vI3d6zBmTH/q8ISHTb+7NZV7P9ELW+rWcH3D7ZR95UD/LShg2Aovn7hmcXv7+iUGbmwqIZWL66MJMry0mL+7Hs2FJBgV/zuWFfMnx0NU8EQX9zXRFleGg9sK1vUWHnpSfyvt2xk71/fwhpXOp/+7Ql2fuMFXjorl1hHWvho/rqCDMNikEQuFkxrTUPbAJtX5ca8bSdML/btKHey73g3oTiYbf7wpXO09o3w2fvWkeiIzI/mhqIsfvH+LXzrT27APzbFO/6znr/6yZG434MfS26Pn7K8NDKSEwyLQRK5WLD2gVEu+CfYEqNth1eyq7qQbt84h89dNCyGSBgYnuDrT7VwW7mT2ytdER1bKcV9Gwt4+mM7+Ohd5ew/2ccdX3uWrzx+Sm5cioBGj48qA+vjIIlcLELDpfp4bBc6Z7tzXT7JCTbLl1e+9mQLo5NBPnffuqi9uklOsPM3d6zlmY/v4N4Ny/nm/jPc/tUD/PaV83HxisYIvtEpzl8cM3ShEySRi0VoaPOSl57Eamfs6+NhaUkO7lyXzyMneggErXkYpsnj52eHOnj3lhLW5ke/zlqQlcLX3349v/7LreRnJvORXxzjj/7jRV7tHIz6s+ONu3t6odOoo/lhksjFgmitqW8dYHOM949fye7qQrwjkxy04EKe1pov7HOTlZLAR+4sj+mzbyxZxn/91Xb+9a0bOX9xjD/41kE++stXueCXdrlz5e4y5rLly0kiFwvS6R2j2zfOFgO2HV5uR4WTjGSHJQ8HPdbYQ32rl4++qYKs1NgvltlsirfVrGT/x2v5y9rV7DvWTd1XDvCt/WekXe4cuD0+lmcmk5s+/62ikSSJXCxIfRTv55yvJIedu9cv5wl3j6WSz/hUkC890kzl8gzecdNKQ2NJT3Lwd3dX8uRHb+OWNXn86+OnuOvfnuWxxp64O3AVSW4DW9fOJolcLEh96wDL0hJZ6zKmSdDldm8qZGgiwIFT1rm05LvPt3L+4hif31mFw26OH8WS3DS+854afvynm0lJsPMXPz7CO7/bwMme+Dl0FSljk0HO9g2z3sCj+WHm+O4RlhPuP250fTxs66pc8tITLXPhRI9vnP9z4CxvXp/PtjV5RofzOreszeORv7mVL96/nqZuP/f++/N89r9O4B2ZNDo002ju8RPSxtfHQRK5WIBO7yhdg2OGHMu/Gofdxr3XFfBU8wWGLbA3+suPnSQQ1HzmXvPeU+6w23j31lIOfLyW92wt5WeHOqn91/08eLCNKYvuEIokt8ccC50giVwsQMNM//Etq42vj8+2u7qQiUCIp5ouGB3KNR3tuMhvXuniz24tozg3dq1/Fyo7NZF/2L2eRz90K9Urs/nHvU3c8+/P82yLdcpY0dDk8ZGVkkBRdorRoUgij4QT531874U2o8OImYbWAbJTEyh3Gddb4kpuKM6hMCuZ35m4vBKaub7NlZHEX9WtMTqceSnPz+CH77uZ/3xPDYFgiPd+/xD/44eHLbXAHEluj58NRZmmKC9KIl+kyUCID/38Fb64r4nGrqVxf2J92wA3ly7DZsBt4ddisyl2VRfyXEsfF01ay/3tK10c6xzk7+6uJD3JYXQ486aU4q6qfB7/yG186I61PNl0gf0nl95FFlPBECe7hwzteDibJPJF+uFL7bT2j+CwKR56sd3ocKLOMzhGp3csZvdzzteu6kICIc1j7h6jQ3mdkYkA//LYSapXZvOH1xcZHc6iJDnsfPD2NWQmO5bkjURneoeZDIZMUR8HSeSL0j88wb8/dZraCifvuLmY373qoT/OL8FtuLR/3DwLnbOtL8xkVV6aKQ8H/Z8DZ+gdmuDzO6tM92pmIRx2G7eWO9l/qm/J7TX//UKnzMgt76tPnGJsKshn76vivdtKmQyG+GlDh9FhRVX9WS+ZyQ4ql5tjJnI5pabLK/VtA6Y6at4xMMp/Pt/GH15fxI0lOUaHEzF1FS76hiYuJbalorHLR0qC3ZA+/FciiXyB3B4fP3+5k/dsLWWNK501rnRuK3fyo/pzcX2TeUPbADeX5WI38YxyV3UhWsPDx7uNDuWS//lIM3al+Lu7K40OJaJ2lDsBOLDEyitNHj/rCjJM83MgiXwBtJ7eeZCTmsiH7lh76f17tpfSNzTBIyfMk0Aiqcc3TvvAqKH9x+dijSudqoJM0+xeefFMP4+5e/hA3WqWZyUbHU5EOTOS2Lgii/0WOlG7WKGQpqnbb5qyCkgiX5BHTvRwqM3Lx95U/ppGRzvWOlmVl8aDB9vismZ4qT5uYP/xudq9qZBXOwfpGDD2JpxAMMQX9jWxIieFP7t1laGxREtthYtXOi4yOGrOnUKR1uEdZXgiwIYi85QXJZHP0/hUkP850+jo7TcVv+ZjNpvige2lHDvv42hH/PV2rm/1kpHkMPw2lLnYubEAgL3HjZ2V//zlTk72DPHpe9eRnGA3NJZoqatwEtLw3Ol+o0OJiUYTXLZ8OUnk8/Sd51rpGhzj73etv2J97I9uWEFGsiMutyI2tA1wU9ky09QFr2VFTio3luQY2nvFNzrFV584xeayZdyzYblhcUTbxhXZLEtL5MAS2U/u9vhx2BRr883RMA4kkc9Lt2+Mbx84yz0blrP1KsfT05Ic/HHNSh490U2Pzzy7Jhar1z9Oa9+I6evjs+2uLuRkzxAtF4YMef7Xn27BNzbF53dVmeL0X7TYbYod5U4OtPQtiSvj3B4/a/MzSHKY5xWWJPJ5+JdHTxLUmk/fu+6an/eeraUEteZH9e2xCSwGwv1VrFAfD7v3ugJsCkP2lJ++MMQPXzrH228uNtVL8GiprXDiHZnkeJyfbtZa4+7yscFk5UVJ5HN05JyX/3rVw/tvXcXKZddudFScm8qd6/L5aUNH3PShaGgbID3JYZqTbHPhzEhi+5o89h73xHTxefr6tiZSE+187K7YXt9mlNvWOrEp4v64/gX/BAMjk6b7OZBEPgfhRkf5mUn8Ze3qOX3Nnu2lXByd4r9ftfbt7mH1rV5qSnNMcwHCXO3aWMi5gVGOn4/dTPGZk708f7qfD92x1vArwGIlJy2R64tz4n4/uTu80GmCyyRms9ZPpUF+ffQ8x8/7+OQ9laTNsdHR1lW5VC7P4MGD7Zbfitg/PMGZ3mFLlVXC3rxhOYl2W8z2lE8GQvzTw82scqbxnq2lMXmmWdSWOzl23kffUPy2qXB7/CgF6wpkRm4pwxMBvvz4Ka4vzub+6rk3OlJKsWd7KSd7hnip1Xq3u892KFwft9BCZ1hWSgI7KpzsO+6JyULcD15sp61/hM/trCLRsbR+vOoqXQA8F8d9yhu7fJTlppmuc+XS+k5bgG/tP0Pf0AR/v2v9vBsd3b+piJzUBB482B6d4GKkvnWA1EQ715ns5eRc7aou5IJ/gkPt3qg+p29ogv/99GnqKpzUVbii+iwzqirIxJmRFNfdEN0evynPUUgiv4ZzAyN87/k23nJDEZtWZs/765MT7PzJ5mKear5Ap9fYE4aL0dDq5caSHBIsVh8Pu3Odi5QEe9TLK5eaqO007/Vt0WSzKWrLnTzX0kcgDq+CGxydpGtwzJS7kKz5kxkjX3q4GYd9cY2O3rWlBJtS/MCiB4S8I5OcujBk2v7jc5Ga6OCuqnwePdEdtbsmG7t8/OJwJw9sK2W10zwHRWKtrtKFfzzAq53xd7K5aabDo5mO5odJIr+Kg2f6eaLpAh+oW0N+5sIbHRVkpXDPhuX84nAnIxa4FPhyh2b6q1jpINCV7Kou5OLoFC+cifwxcq01X5hpovbBWU3UlqJb1uZht6m4LK+Y8Wh+WEQSuVLqbqXUKaXUGaXUJyMxppECwRBf2NvEymUp/OktZYseb8/2MobGA/z66PkIRBdb9a1ekhNsXFc0/9KSmdxWnkdmsoO9UTgc9PCJbg61e/n4myrISkl44y+IY5nJCdSU5LD/ZPwteLo9fgqyklmWlmh0KK+z6ESulLID3wLuAaqAdyilLF0k/NmhDk5dGOIzEWp0dENxNtUrsnjoYLvljjDXtw5wY0mO5XdgJDns3LOhgCeaLkT0kNbYZJD/9chJ1hVk8sc3rYzYuFZWV+miqdsfVy0qYDqRm+0gUFgkfjpvBs5orVu11pPAz4H7IzCuIQZHJ/nqky1sXZXLm9dHptHR9FbEMlr7R3j2tHVmKoOjM/VxC+4fv5Jd1YUMTwQievrw903UqizRTCwWwjt2nm2Jn/LK6GSA1r5hU5ZVIDKJvAjonPX38zPvew2l1PuVUoeVUof7+sybzL7+1Gn8UWh0dO91Bbgykiy1FfFQmxetYbOFFzpn27o6l7z0pIjtXvEMjvHtZ89w33UFll4MjrTy/HQKs5LjqrzS3D1ESBPXM/I50Vp/R2tdo7WucTqdsXrsvLRcGOJH9ef4k83FET+5leiw8a4tJTzX0seZ3uGIjh0t9a1ekhw2qleacxYyX3abYufGAp4+2cvQ+NSix/vnR08S0vDJe+Lr+rbFUkqxo8LFC2f64+bawyaTHs0Pi0Qi7wJmFwdXzLzPUrTWfHFfE2mJdj56V0VUnvGOm4tJtNsssxWxoW2AG4pzTNWuc7F2VRcwGQjxZNOFRY1zuN3L7455+PPb3riJ2lJUV+FkeCLA4XPRPYQVK26Pn5zUBApNelVfJBL5y8BapVSZUioReDvwuwiMG1NPN083OvrIXeVRW5V2ZiSxq7qQXx89j29s8TPCaPKNTdHU7bfksfxruaE4h6LslEWVV8JN1JZnJs+5idpSs31NHgl2xYE4ucuz0eNjfWGWafvKLzqRa60DwF8DjwPNwC+11u7FjhtLE4Eg//RwE2tc6bxrS0lUn7Vneymjk0F++XLnG3+ygV4O18fjZKEzTCnFrupCXjjdj3dkYXdM/uroeU50TTdRS000V88Ns0hLcrC5LDcu2tpOBUO09Aybtj4OEaqRa60f0VqXa61Xa62/FIkxY+mhg+20D4zyuZ1VUT+GvqEoi5tLl/GDl9oJmngrYkPbAIkOG9cXW3v/+JXsqi4gENI82tg9768dGp/iy4+d4obibO7fVBiF6OJHbYWT073DnL9o3fYUAKcvDDMZDJmyx0qYtTcHR0Df0ATfeOYMd1S62FEem0XYPdtLOX9xbNF12mhqaPOyaWV2XF4YXFWQyWpn2oJuDvrm/jP0D083UTPry2yzCHdDtHp5JdyDfINJFzpBEjlfefwUE4Egn7nv2te3RdJdVfkUZafw4MG2mD1zPvzjUzR2+eJ2S51Sit3VRRxq987r0Ep7/wjff6GNP7phBdULaKK21KzKS6N4WarlL5twe/ykJtopy00zOpSrWtKJ/MR5H7880sme7WWsimGjI4fdxnu2ltDQ5r3UiMdMjrRfJKRhS1l8LXTOtqu6AK1h3/G5z8q/9EgziXYbf3d3dHY1xRulFHUVTg6eGbD0lYduj491BZnzbmMdS0s2kWut+ce9bpalJvLXt6+J+fP/+KaVJCfYeOhF883K69sGSLArri/OMTqUqFnlTGdDUSZ757h75fnTfTzZdIEP3L4G1yKaqC01tZUuxqaCly4nsZpQSNNk4qP5YUs2ke893s3hcxf5xJsryEyOfaOj7NRE3nLDCv7rVQ8Dw+a6Gqu+dbo+npIYf/Xx2XZXF3LsvI/2/pFrfl64iVrxslTet33xTdSWkq2rckly2CzbDfGcd5SRySAbTHo0P2xJJvLpRkfNrC/M5G01xjU62rOtlMlAiJ8d6jAshssNTwRo7PLF3bbDK9m5cXrXyRuVV37S0MHp3mE+c19kmqgtJckJdratzrXsgmdj1/RCp5l3rMASTeT/97mzdPvG+ftd6w1tdLQ2P4Nb1+bxo/pzUbvwYL6OnLtIMKTj7iDQlRRmp3BTac41DwddHJnka0+2sG11Lm+qyo9hdPGjtsJFW/8IbW/wyseM3B4/CXZFeX6G0aFc05JL5F2DY/zHs2fZubGAm02wmLdneykX/BM8cmL+e5qjob51AIdNcWNJ/NbHZ9tdXUjLhWFO9lx50fnrT7UwNB75JmpLSbgbohV3r7g9PsrzM0zfxtnc0UXBPz96Eq3hU/fGbrvhtdSWuyjLSzNNV8SG1gE2rshaMicW77muALtNXXHR81TPED9u6OCdm0uoXG7ul9ZmVpybyipnGvstVl7RWpu6B/lsSyqRH2rzsveYhz/fsZqi7BSjwwGmL6x979YSXu0c5JWOi4bGMjoZ4Ph5X9y0rZ2LvPQktq3OZe+xbrT+/UlbrTVf2OcmPcnBR+8qNzDC+FBX4aK+dYCxSetsQ+zxj+MdmTRtD/LZlkwiD4WmfzALspL5ix2rjA7nNd5as5L0JAcPGdwV8ci5iwRCOm4PAl3N7upCOryjr7kw+MmmCxw8M8BH7lxLjgmv9rKaugoXk4EQL7VG/s7UaHF3TZfbZEZuIr86cp7GLr8pGx2lJzl4W80KHj7ezQW/cddjNbR6sS+h+njYmzcsJ9Fuu7ToOd1ErZm1rnTeGeUmakvFTWU5pCbaLXXZhNvjRykifjdBNCyJRD40PsWXHz9JTUkOu6vN2ejogW2lBLXmx/XnDIuhoW2ADUVZpCeZ6xddtGUmJ1Bb4eTh490EQ5rvv9BOhzc2TdSWiiSHne1r8th/qvc1JSwza/T4KMtLI80CPw9L4rv0m8+cYWBk0tSNjkpy07ij0sVPGzoMOc48Nhnk1c5BtiyBbYdXsntTIb1DE+w77uGbz5zmznUubotRE7Wloq7CxfmLY5zts8YNWdMnOs1fH4clkMjb+kf4/sE23nrDCq5bYe7/KXu2lzEwMhmxOyXn45WOi0wFddxctDxfd1Tmk5po5xO/Os5kMMRn7qsyOqS4U1sx/YvRCuWViyOTdA2OWaI+DksgkX/p4SYS7TY+YYFGR9tW51KRn8GDB9tj/vKzvnUAm4Ka0qVVHw9LSbRzV1U+k4EQ79teRlmeeTvdWVVhdgqVyzMscVy/qXt6odPsR/PD4jqRP9fSx1PNvXzwjrW4Mszf6EgpxQPbS2nu9tMQ4yZD9W1eNhRlkWFA3xmz+NNbyrhzXb4hTdSWih0VTl5u90bk8utoCh/Nlxm5waaCIb64r4mS3FT2bC81Opw5+4NNRWSnJvBQDA8IjU9N18c3m4FZCmkAABO1SURBVOCkq5E2rsjmu++tWdK/zKKtrsLFVFBz8MyA0aFck9vjpzAr2TJbT+M2kf+k/hyne4f57H1VlroFPiXRzttvKuaJph46vbG5IuuVjkEmA6El0ShLGOvGkhwykhymP67v9vhYb+IbgS4Xl4ncO9Po6JY1edy5zmV0OPP2nq0lKKX4UYy2Ija0DaAU3LTEZ+Qi+hLsNm4tN/c2xJGJAK39I5Ypq0CcJvJ/e7KFkckgn9tpzUZHhdkp3L1+OT8/1MHoZCDqz2to9VJVkElWipQURPTVVri44J+guXvI6FCu6GSPH62xzNZDiMNEfrLHz08azvGuzcVULDd368lr2bO9FP94gF8f7YrqcyYCQY52XFxyx/KFcWpn9ucfaDFnecXtsc7R/LC4SuRaa76wt4nMlAQ+YvFGRzeW5HBdURYPHWwjFIreS9BjnT4mAqElv9ApYseVmcyGokwOmHQ/ubvLz7K0RAqyzL/TLSyuEvkTTRd48ewAH72rnOxUa6w2X41Sij3bSznbN8LzZ6LXaKihdbo+bobe7GLpqKtwcaTjIr5R821DbPT4WF+YaamybNwk8vGpIF96uJny/HT+5OZio8OJiPs2FpCXnsSDB6N3QXN92wCVyzMt/4tPWEtthYtgSPP8GXPNyicDIVouDJn+arfLxU0i//7BNjq8o3x+53occdLoKMlh552bizlwqo/WKPSnmAyEOHLuopRVRMxtWplNdmqC6Y7rn+4dYiqoLbXQCXGSyHv943zrmTPcVZXPLWvzjA4not65pZgEu+IHUehVfqJrkPGp0JJtlCWMY7cpdpQ7ebalN6prQPMVXujcIDPy2Pvy46eYCmo+Y5Lr2yLJlZHMro2F/OrIefwRPtZc3zrdBuBmOQgkDFBb4aR/eJJGj8/oUC5xd/lIS7RTmmutXjuWT+THOgf51ZHzvO+WMkrjtNHRnu1ljEwG+eXLnREdt751gIr8DJZZ5BiyiC+3rXWilLm6Ibo9ftYVZGKzWWehEyyeyLXW/MNeN86MpLhudHTdiixqSnL4wUvtBCP0MnQqOFMfl7KKMEhuehLVK7JN0w0xFNI0dfvZYKGj+WGWTuT//aqHVzoG+cSbK+L+Vps928vo9I7xdPOFiIx3osvH6GRQDgIJQ9VVuDh2fpCB4QmjQ6FtYITRyaDldqyAhRP56GSAf370JNcVZfHWG1YYHU7UvXl9PgVZyTwYoa6IDZfq4zIjF8apq3SiNTx32vjyihVPdIZZNpH/x4Gz9PjH+YfdVZarZy2Ew27j3VtLeKl1gJM9/kWP19A2wBpXOnnpSRGIToiF2VCYRV56IgdOmSGR+0iwK9a6rNfaw5KJvNM7yv99rpX7NxVyY8nSmVG+46ZikhNsi+5VHgiGeLnNK9sOheFsNsWOchfPtvRFbP1noZo8fiqWZ5DosF5atF7EwD8/ehKbUnzynkqjQ4mpnLRE/vD6In77ShfekckFj+P2+BmZDEr/cWEKdZVOBkeneLVz0LAYtNY0dvlYX2C9hU5YZCJXSv2rUuqkUuq4Uuq3SqnsSAV2NfWtAzx8opu/rF1NQVZKtB9nOg9sK2MiEOJnhzoWPEZ96/TtLLJjRZjBrWuc2G3K0Msmun3jXBydYn2R9erjsPgZ+ZPABq31RqAF+NTiQ7q6YGi6u2FRdgrvv21VNB9lWhXLM9i+JpcfvXSOqWBoQWM0tHlZ5UyzxD2mIv5lpSZwY3GOodsQrbzQCYtM5FrrJ7TW4ZsP6oGobh/55eFOmrr9fOreSpITrHN9W6Tt2VZGj3+cxxp75v21wZDm5TavlFWEqeyocNLY5afXP27I890eH0rBuoIlmMgv8z7g0at9UCn1fqXUYaXU4b6+ha1Qj0wEuK3cyX3XFSw0xrhwe6WLktzUBXVFbPL4GZoIyEKnMJW6iukrGQ+0GLN7pbHLz6q8NFITrXke5Q0TuVLqKaVU4xXe7p/1OZ8BAsBPrjaO1vo7WusarXWN0+lcULB/dusqfrDnJkv1CY4Gm03xnq2lHO0Y5Ng8F4ga2mbq4zIjFyayriCD/Mwkw+rkTR6f5ToezvaGiVxrfafWesMV3v4bQCn1ALATeKeOwW2qSz2Jh72tZgVpiXYemmdXxPpWL6W5qSy30O0nIv4ppaircPF8S/+C134Wyjsyicc3btn6OCx+18rdwN8Cu7XWo5EJScxFZnICb6tZyb7jnjnXFYMhzaG2ATmWL0yptsLF0ESAI+cuxvS57pnui1bssRK22Br5N4EM4Eml1KtKqf+IQExijt67rZRASPPjhrltRTzZ48c/HpBth8KUtq/JJcGuYr57xeo7VmDxu1bWaK1Xaq03zbz9RaQCE2+sLC+NugoXP204x0Qg+IafH+6vIvVxYUYZyQncVLqMZ2N8XN/t8VOUnWLp6w4tebJT/N6e7aX0D0+y91j3G35ufesAxctSKcxeegephDXUVbg42TOEZ3AsZs90z1y2bGWSyC3uljV5rHGl8+DBNq611hwKaQ61e+V+TmFqdZXTO9pi1URrZCJAW/+IpXesgCRyy1NK8cC2UtwePy+3X32RqKV3iMHRKTbLQqcwsdXOdFbkpMSsTt7c7Udra9fHQRJ5XHjLDUVkJjt46MWrHxCqPxvePy4zcmFe4W2IB8/0z2ndZ7EuLXRatMdKmCTyOJCa6OAdNxfzuPsCXVepLTa0eSnKTmHlstQYRyfE/NRWOBmdDPJyW/S3Ibo9PnLTElmeae1zFZLI48S7t5agteaHL7W/7mNaaxravLLtUFjC1tW5JDpsMSmvNHb5qSrMtPxBQ0nkcWJFTipvXr+cnx/qZHQy8JqPne4dxjsyKQeBhCWkJjrYsio36ol8MhDidO+Q5Rc6QRJ5XNmzvQzf2BS/faXrNe9vmOk/vkX2jwuLqKtw0to3wrmBkag9o+XCEFNBbfmFTpBEHlduKs1hfWEmDx1sf81WxPo2LwVZyaxcJvvHhTVc6oYYxW2I8XA0P0wSeRwJb0U83TvMC2f6gZn6eOt0fxWr1wHF0lGal0ZZXlpUyytuj5/0JAclcbABQBJ5nNlVXUhuWuKlC5rP9o3QPzwp2w6F5dRWOHnp7ADjU9HZhuj2+FlXkIHNZv0JjiTyOJOcYOedm4t55lQv7f0jv+8/LgudwmLqKlxMBEK8NLPGE0nBkKa52x8XC50giTwuvWtLCQ6b4qEX26lv9ZKfmURprvVfPoql5eayZaQk2DlwMvLllbb+EUYng3Gx0AmSyOOSKzOZ+64r4FdHzvPS2X42l0l9XFhPcoKd7Wty2X+q75p9hBYivNApM3Jhanu2lzE8EaB/WPaPC+uqrXDR4R2ltT+y2xCbPH4S7TbW5qdHdFyjSCKPU9Urs7mhOBtATnQKy6qtmO6GuD/C5RW3x0/F8gwS7PGRAuPjXyGu6NP3ruOBbaWsykszOhQhFmRFTiprXekR3U+utaYxDnqQz+YwOgARPTWly6gpldm4sLa6ShcPHmxjZCJAWtLiU5bHN87g6FRcJXKZkQshTK22wslUUHNw5pDbYrm7phc6q+JkoRMkkQshTK6mZBnpSQ72R6i80ujxY1OwriAjIuOZgSRyIYSpJTps3LImjwOneiOyDbHJ42OVM53UxPipLEsiF0KYXl2lk27fOC0Xhhc9ltvjj6v6OEgiF0JYQO1MN8TFNtEaGJ6g2zfOhjiqj4MkciGEBeRnJlNVkLno/eSX7uiUGbkQQsReXaWTw+cu4h+fWvAY4UReJYlcCCFir7bCRTCkeeH0wrchuj0+irJTyE5NjGBkxpNELoSwhOtXZpOZ7FhUeaXJ42dDUXzNxkESuRDCIhx2G7eVOznQ0kcoNP9tiMMTAVr7R+Km4+FsksiFEJZRV+Gib2iCpm7/vL+2uTs+FzpBErkQwkJ2LKIbYvhovszIhRDCQHnpSVSvyFrQfvJGj5+89ETyM5OiEJmxJJELISyltsLFK52DXByZnNfXuT1+qgqz4vK2LEnkQghLqat0oTU8d3ruTbQmAkFOXxiKy/o4SCIXQljMxqIsctMS53XZxOkLwwRCOu6O5odJIhdCWIrNpthR7uTZlj6Cc9yG2HhpoVNm5FellPqYUkorpfIiMZ4QQlxLbaUL78gkx88Pzunz3R4/6UkOipelRjkyYyw6kSulVgJvAjoWH44QQryx29bmYVPM+bIJt8dHVUEmNlv8LXRCZGbk/wb8LbD4ju9CCDEH2amJXF+cw4E5bEMMhjTN3UOsj8Oj+WGLSuRKqfuBLq31sTl87vuVUoeVUof7+iJ3I7YQYmmqq3By/LyPvqGJa35eW/8wY1PBuDwIFPaGiVwp9ZRSqvEKb/cDnwY+P5cHaa2/o7Wu0VrXOJ3OxcYthFjiwpdNPNty7YlhvPYgn+0NL63TWt95pfcrpa4DyoBjMxvsVwBHlVI3a617IhqlEEJcZn1hJq6MJPaf6uWtN6646ue5PX4SHTbWuNJjGF1sLfj2Ua31CcAV/rtSqh2o0VovvFmwEELMkVKK2gonjzb2EAiGcNivXGBo7PJRuTyDhKt8PB7E779MCBH36ipcDI0HONpx5W2IWuu4vGz5chFL5FrrUpmNCyFiafvaPBw2ddXdK12DY/jGpqiK44VOkBm5EMLCMpMTqCnNuep+8vBC5waZkQshhHnVVbho7vbT4xt/3cfcXT5sCiqXSyIXQgjTCm9DvFJ5xe3xs9qZTkqiPdZhxZQkciGEpZXnp1OYlXzFyyaWwkInSCIXQlicUoraShcvnO5nMhC69P7+4Ql6/ONsKIrvhU6QRC6EiAN1FS5GJoMcbvdeel94obNKZuRCCGF+21bnkmi3vaa84vbM9CAvkBm5EEKYXlqSg82rlr1mG6Lb42dFTgpZqQkGRhYbksiFEHGhtsLFmd5hOr2jwPTWw3i92u1yksiFEHGhrmK6q+qBU70MjU/RPjC6JHaswCKaZgkhhJmU5aVRkpvKgVN9VMwcAIrnyyRmkxm5ECIuKKWoq3Bx8Gw/RzsuAkhpRQghrKa2wsn4VIgfvthOXnoSrsxko0OKCUnkQoi4sWVVLkkOGx7f+JKpj4MkciFEHElOsLNtdS4Q31e7XU4SuRAirtRVTjfRWgpH88Nk14oQIq7cv6mIcwOj7ChfOpe8SyIXQsSVrJQEPrezyugwYkpKK0IIYXGSyIUQwuIkkQshhMVJIhdCCIuTRC6EEBYniVwIISxOErkQQlicJHIhhLA4pbWO/UOV6gPOLfDL84D+CIYTKRLX/Ehc8yNxzY9Z44LFxVaitX7dkVVDEvliKKUOa61rjI7jchLX/Ehc8yNxzY9Z44LoxCalFSGEsDhJ5EIIYXFWTOTfMTqAq5C45kfimh+Ja37MGhdEITbL1ciFEEK8lhVn5EIIIWaRRC6EEBZnqUSulLpbKXVKKXVGKfVJo+MBUEp9XynVq5RqNDqW2ZRSK5VS+5VSTUopt1LqQ0bHBKCUSlZKHVJKHZuJ6x+Njmk2pZRdKfWKUmqf0bGEKaXalVInlFKvKqUOGx1PmFIqWyn1K6XUSaVUs1Jqqwliqpj57xR+8yulPmx0XABKqY/MfM83KqV+ppRKjtjYVqmRK6XsQAtwF3AeeBl4h9a6yeC4bgOGgR9qrTcYGctsSqkCoEBrfVQplQEcAf7ABP+9FJCmtR5WSiUALwAf0lrXGxlXmFLqo0ANkKm13ml0PDCdyIEarbWpDrgopX4APK+1/q5SKhFI1VoPGh1X2EzO6AI2a60XegAxUrEUMf29XqW1HlNK/RJ4RGv9UCTGt9KM/GbgjNa6VWs9CfwcuN/gmNBaPwd4jY7jclrrbq310Zk/DwHNQJGxUYGeNjzz14SZN1PMJpRSK4D7gO8aHYvZKaWygNuA7wForSfNlMRn3AGcNTqJz+IAUpRSDiAV8ERqYCsl8iKgc9bfz2OCxGQFSqlS4HqgwdhIps2UL14FeoEntdamiAv4OvC3QMjoQC6jgSeUUkeUUu83OpgZZUAf8OBMKeq7Sqk0o4O6zNuBnxkdBIDWugv4CtABdAM+rfUTkRrfSolcLIBSKh34NfBhrbXf6HgAtNZBrfUmYAVws1LK8JKUUmon0Ku1PmJ0LFdwi9b6BuAe4AMz5TyjOYAbgG9rra8HRgBTrFsBzJR6dgP/z+hYAJRSOUxXEMqAQiBNKfWuSI1vpUTeBayc9fcVM+8TVzFTg/418BOt9W+MjudyMy/F9wN3Gx0LsB3YPVOP/jlwu1Lqx8aGNG1mNofWuhf4LdNlRqOdB87PejX1K6YTu1ncAxzVWl8wOpAZdwJtWus+rfUU8BtgW6QGt1IifxlYq5Qqm/lt+3bgdwbHZFozi4rfA5q11l8zOp4wpZRTKZU98+cUphevTxobFWitP6W1XqG1LmX6e+sZrXXEZkwLpZRKm1msZqZ08SbA8B1SWuseoFMpVTHzrjsAQxfSL/MOTFJWmdEBbFFKpc78bN7B9LpVRDgiNVC0aa0DSqm/Bh4H7MD3tdZug8NCKfUzoBbIU0qdB/5ea/09Y6MCpmeY7wZOzNSjAT6ttX7EwJgACoAfzOwosAG/1FqbZqufCeUDv53+2ccB/FRr/ZixIV3yQeAnMxOrVmCPwfEAl37h3QX8udGxhGmtG5RSvwKOAgHgFSJ4VN8y2w+FEEJcmZVKK0IIIa5AErkQQlicJHIhhLA4SeRCCGFxksiFEMLiJJELIYTFSSIXQgiL+/8DdKFIavxedgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "x =  range(len(nums))\n",
    "y = nums\n",
    "\n",
    "# plot函数作图\n",
    "plt.plot(x, y)  \n",
    "\n",
    "# show函数展示出这个图，如果没有这行代码，则程序完成绘图，但看不到\n",
    "plt.show()  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果有一段是负收益的时候,就不考虑"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义`dp[i]`, 表示 从开始到`nums[i]`位置时的最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "转移方程\n",
    "\n",
    "$$\n",
    "dp[i] = \n",
    "\\begin{cases}\n",
    "  & \\text{ dp[i]-1+nums[i] }, dp[i-1]> 0 \\\\\n",
    "  & \\text{ nums[i] } , dp[i-1] \\le  0\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if dp[i-1] > 0:\n",
    "                dp[i] = dp[i-1] + nums[i]\n",
    "            else:\n",
    "                dp[i] = nums[i]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Solution().maxSubArray(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 总结"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有点像买股票那题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
